#include <stdio.h>
#include <stdlib.h>

// 实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列

typedef struct Node *PtrToList;
struct Node
{ // 结点定义
    int Data;
    PtrToList next;
};
typedef PtrToList List;

List Read();                  // 创建链表
void Print(List L);           // 打印链表
List Merge(List L1, List L2); // 合并链表

int main()
{
    List L1, L2, L3;
    L1 = Read();
    L2 = Read();
    L3 = Merge(L1, L2);
    Print(L3);
    Print(L1);
    Print(L2);
    return 0;
}

List Read()
{
    /* List head, p;
    p = head;
    p = (List)malloc(sizeof(struct Node)); // 分配空间
    int n;
    scanf("%d", &n);
    while (n > 0)
    {
        scanf("%d", &p->Data);
        p = p->next;
        p = (List)malloc(sizeof(struct Node)); // 分配空间
        p->next = NULL;                        // 确保尾结点的指针域为NULL
        n--;
    }
    return head; */ //这里的创建链表方式存在问题
    List head, tail, p;
    int n,x;
    head = NULL, tail = NULL;//链表一开始为空
    scanf("%d", &n);//将要输入n个数
    while(n > 0)
    {
        p = (List)malloc(sizeof(struct Node));
        scanf("%d", &x);
        p->Data = x;
        if(head == NULL)
            head = p;
        else
            tail->next = p;
        tail = p;
        n--;
    }
    if(tail != NULL)
        tail->next = NULL;//确保尾指针的指针域为NULL
    return head;
}

List Merge(List L1, List L2)
{
    /* List head,p;
    head = (List)malloc(sizeof(struct Node));
    head->next = NULL;
    p = head;//p用作myNODE的遍历指针
    List p1 = L1, p2 = L2; // p1,p2均是移动指针
    while (p1 != NULL && p2 != NULL)//循环中的计算仍然会执行，因此当p1或p2到头后，计算p1->data就会报错！！！
    {
        List NewNode = (List)malloc(sizeof(struct Node));
        NewNode->next = NULL;
        if (p1->Data >= p2->Data)
        {
            NewNode->Data = p2->Data;
            p2 = p2->next;
            p->next = NewNode;
            p = p->next;
        }
        else
        {
            NewNode->Data = p1->Data;
            p1 = p1->next;
            p->next = NewNode;
            p = p->next;
        }
    }

    return head; */
    List dummy = (List)malloc(sizeof(struct Node));//哑结点
    List p = dummy;
    List p1 = L1, p2 = L2;
    while(p1 !=NULL && p2 != NULL)
    {
        List NewNode = (List)malloc(sizeof(struct Node));
        NewNode->next = NULL;
        if(p1->Data >= p2->Data)
        {
            NewNode->Data = p2->Data;
            p->next = NewNode;
            p2 = p2->next;
            p = p->next;
        }
        else
        {
            NewNode->Data = p1->Data;
            p->next = NewNode;
            p1 = p1->next;
            p = p->next;
        }
    }
    if(p1 != NULL)
        p->next = p1;
    else
        p->next = p2;
    List MergedList = dummy->next;
    free(dummy);
    return MergedList;
}

void Print(List L)
{
    List p = L;
    if (p == NULL)
        printf("NULL\n");
    else
    {
        while (p != NULL)
        {
            printf("%d ", p->Data);
            p = p->next;
        }
        printf("\n");
    }
}
